1. Field of the Invention
The present invention relates to adaptive difference computing elements and motion estimation apparatuses, and more particularly to an adaptive difference computing element and motion estimation apparatus dynamically adapting to input data with a reduced amount of circuit operation.
2. Description of the Background Art
A motion estimation apparatus is used in a moving picture compression system for MPEG (Moving Picture Experts Group) and performs a large number of computations. To date, various computation algorithms for the motion estimation apparatus have been proposed. For the moving picture compression system for MPEG, xe2x80x9cVLSI Architectures for Video Compression-A Surveyxe2x80x9d, by P. Pirsch et al., Proc. IEEE Vol. 83, No. 2, pp. 220-246, 1995 and xe2x80x9cULSI Realization of MPEG2 Realtime Video Encoder and Decoder-An Overviewxe2x80x9d, by M. Yoshimoto et al., IEICE Trans. Electron., Vol. E78-C, No. 12, pp. 1668-1681, 1995 are incorporated herein by reference.
In addition, for an LSI (Large Scale Integration) for motion estimation computation, xe2x80x9cA Half-pel Precision MPEG2 Motion-Estimation Processor with Concurrent Three-Vector Searchxe2x80x9d, by K. Ishihara et al., ISSCC Digest of Technical Papers, pp.1502-1509, 1995 and xe2x80x9cA Motion Estimation Processor for MPEG2 Video Real Time Encoding at Wide Search Rangexe2x80x9d, by A. Ohtani et al., Proc. IEEE Custom Integrated Circuits Conference, pp. 405-408, 1995 are incorporated herein by reference.
In the moving picture compression system for MPEG, difference must be calculated between pixel values (sample values) of a reference block and one of blocks to be searched corresponding to one of a large number of candidate vectors within a search range. Most of the computation performed by a whole system is the computation performed by the motion estimation apparatus. Therefore, it is critically important that difference calculation is performed by a circuit with power consumption which is as small as possible in order to achieve a moving picture compression system with reduced power consumption.
To cope with this subject, an encoding apparatus 220 has been proposed which is shown in FIG. 1. Encoding apparatus 220 includes: a rounding circuit 201 rounding lower bits of a prescribed number of bits in accordance with an output from a quantization circuit 204, which will later be described, for every sample of image data of a current frame which has been input from a video input; a frame memory 208 connected to an output of an addition circuit 212, which will later be described, for storing image data; a rounding circuit 207 rounding lower bits of a prescribed number of bits in accordance with an output from a quantization circuit 204 which will later be described for every sample of image data which has been stored in frame memory 208; a motion estimation computing element 202 receiving image data of the current frame input from the video input and that of a preceding frame stored in frame memory 208 respectively through rounding circuits 201 and 207 and calculating a sum of absolute difference between data elements of a reference block and those of one of blocks to be searched; a selector 211 connected to an output of motion estimation computing element 202 and the video input for selecting and outputting one of the above mentioned output or input; a discrete cosine translation circuit 203 connected to an output of selector 211; a quantization circuit 204 connected to an output of discrete cosine translation circuit 203 for quantizing in accordance with a quantization control signal output from a output buffer portion 210 which will later be described; a variable length encoder 209 connected to outputs of quantization circuit 204 and motion estimation computing element 202; an output buffer portion 210 connected to an output of variable length encoder 209; an inverse quantization circuit 205 connected to an output of quantization circuit 204; an inverse discrete cosine translation circuit 206 connected to an output of inverse quantization circuit 205; and an addition circuit 212 connected to outputs of inverse discrete cosine translation circuit 206 and motion estimation computing element 202 for performing addition of data elements of two blocks and reconstructing the block.
In encoding apparatus 220, an amount of data accumulated in output buffer portion 210 increases as the amount of encoded data increases. Thus, a quantization step value is increased to decrease the amount of encoded data. If the amount of encoded data decreases, conversely, it is controlled to increase. At the time, significant digit numbers of samples of the reference block and one of blocks to be searched applied to motion estimation computing element 202 are determined in accordance with an algorithm shown in FIG. 2. NTB represents the number of non-trancated bits, and lower bits which are not included in the non-trancated upper bits are rounded in rounding circuits 201 and 207. Quantization step values of the current and preceding frames are respectively represented by Qc and Qp. More specifically, if quantization step value Qc is equal to or smaller than quantization step value Qp and NTB is equal to or smaller than a possible maximum value 6, NTB is incremented by 1. Thus, the number of the lower bits to be rounded is decreased. Conversely, if quantization step value Qc is greater than quantization step value Qp and NTB is greater than 1, NTB is decremented by 1. Thus, the number of the lower bits to be rounded is increased. A number of significant bits of data computed by motion estimation computing element 202 can be decreased on the average in accordance with the algorithm. As described above, a method has been proposed which allows power consumption to be reduced by reducing calculation accuracy for adding absolute differences. Encoding apparatus 220 has been disclosed in xe2x80x9cReducing Hardware Complexity of Motion Estimation Algorithms Using Truncated Pixelsxe2x80x9d, IEEE ISCAS""97, 1997, by Zhongli He et al., which is herein incorporated by reference.
The above described encoding apparatus 220 suffers from a problem that the calculation accuracy of the motion estimation computing element is reduced as the lower bits are rounded.
In addition, if calculation is simply performed using data with all bits without rounding the lower bits, a signal change occurs many times which in turn increases power consumed by the circuit.
The present invention is made to solve the aforementioned problem. An object of the present invention is to provide an adaptive difference computing element and a motion estimation apparatus which consumes less power without any decrease in calculation accuracy.
Another object of the present invention is to provide an adaptive difference computing element and a motion estimation apparatus which can reduce the number of signal changes in a calculation circuit without any decrease in calculation accuracy.
Still another object of the present invention is to provide an adaptive difference computing element and a motion estimation apparatus capable of performing motion estimation without any decrease in calculation accuracy while substantially decreasing the number of bits of data to be calculated.
An additional object of the present invention is to provide an adaptive difference computing element and a motion estimation apparatus capable of performing motion estimation without rounding data with reduced power consumption.
Another additional object of the present invention is to provide an adaptive difference computing element and a motion estimation apparatus capable of performing motion estimation without any decrease in calculation accuracy by performing calculation for only a portion of data with reduced power consumption.
Another additional object of the present invention is to provide an adaptive difference computing element and a motion estimation apparatus capable of performing motion estimation without any decrease in calculation accuracy by performing calculation for only a portion of data for which variation in values occurs with reduced power consumption.
An adaptive difference computing element according to one aspect of the present invention includes: a first circuit receiving first and second data with the same bit length and each having bits at one and the other ends, determining if a prescribed relation is obtained between a bit string of the first data and that of the second data for each bit of the first data and corresponding each bit of the second data, and replacing the each bit of the first data and the corresponding each bit of the second data with the same predetermined bit values if the prescribed relation is obtained, and otherwise directly outputting the first and second data; and a subtracter having inputs connected to receive the first and second data from the first circuit.
In calculating a difference between the first and second data, a difference between two data is calculated which have been replaced by bit values predetermined by values of bits which can preliminary predict a difference result. Thus, the number of signal changes is reduced. As a result, an adaptive difference computing element which consumes less power without any decrease in calculation accuracy is provided.
Preferably, the first circuit includes a second circuit determining if the bit string of the first data and that of the second data match for each bit of the first data and corresponding each bit of the second data, and replacing the each bit of the first data and the corresponding each bit of the second data with the same predetermined bit values if they match, and otherwise directly outputting the first and second data.
In calculating a difference between the first and second data, a difference is calculated between two data which have been replaced by bit values predetermined by values of bits which are preliminary found to provide that a difference result of 0. Thus, the number of signal changes decreases. As a result, the adaptive difference computing element which consumes less power without any decrease in calculation accuracy can be provided.
More preferably, the second circuit includes: a plurality of bit string matching circuits provided corresponding to a pair of bits including each bit of the first data and the corresponding each bit of the second data for determining if the pair of bits are equal for every pair of bits and outputting a determination signal; a circuit for outputting the predetermined bit value in a fixed state; and a plurality of selector circuits provided corresponding the plurality of bit string matching circuits, each having an input corresponding pairs of bits of the first and second data and an input receiving predetermined bit values, and being controlled by the determination signal output from a corresponding bit string matching circuit.
An adaptive difference computing element according to another aspect of the present invention includes: a first circuit receiving first and second binary data for determining if upper bit values of bit strings including target bits match for the first and second data; first and second shifters for shifting the first and second data toward the side of an upper bit by the number of bits depending on how many upper bit values of bit strings match; a subtracter for calculating a difference between data from the first and second shifters; and a third shifter connected to the subtracter for shifting back an output from the subtracter toward the side of a lower bit. The bit width of data input to the subtracter is smaller than those of the first and second data.
The data which has been shifted toward the side of the upper bit is applied to the subtracter in accordance with the number of bits of the upper bits which provide 0 for the difference result. Thereafter, the output from the subtracter is shifted toward the side of the lower bit by the prescribed number of bits such that the output from the subtracter is shifted back to the original position. Thus, input and output bit widths of the subtracter are reduced, so that the number of signal changes decreases. Therefore, an adaptive difference computing element which consumes less power consumption without any decrease in calculation accuracy can be provided.
A motion estimation apparatus according to still another aspect of the present invention includes: an input portion receiving a reference frame and an image frame to be searched, extracting a reference block from the reference frame for output and sequentially outputting a plurality of blocks to be searched corresponding to the reference block from the image frame to be searched for the reference block; an absolute difference sum circuit calculating an accumulated sum of absolute difference values between corresponding pixels for each of the plurality of blocks to be searched with respect to the reference block; and an output portion identifying a position of a block to be searched in the image frame which provides the minimum accumulated sum. The absolute difference sum circuit includes: a difference computing element sequentially receiving sample data of the reference block and one of blocks to be searched with the same bit width for calculating an absolute difference value; and a latch holding an accumulated sum. The difference computing element includes: a first circuit sequentially receives sample data of the reference block and one of blocks to be searched, determines if a prescribed relation is obtained between the sample data of the reference block and that of one of blocks to be searched, and replaces upper bits of the sample data of the reference block and one of blocks to be searched with the same predetermined bit values if the prescribed relation is obtained, and otherwise directly outputs the sample data of the reference block and one of blocks to be searched; and a subtracter having inputs connected to receive the sample data of the reference block and one of blocks to be searched from the first circuit.
In calculating a difference between the sample data of the reference block and one of blocks to be searched, a difference is calculated between two data which have been replaced by bit values predetermined by values of bits which can provide a prediction on a difference result. Thus, the number of signal changes decreases. As a result, a motion estimation apparatus which consumes less power without any decrease in calculation accuracy can be provided.
Preferably, the first circuit includes a second circuit determining if a bit string of sample data of the reference block and that of one of blocks to be searched match for each bit, replacing the each bit of the sample data of the reference block and corresponding each bit of the sample data of one of blocks to be searched with the same predetermined bit values if they match, and otherwise directly outputting sample data of the reference block and one of blocks to be searched.
In calculating a difference between sample data of the reference block and one of blocks to be searched, a difference is calculated between the two data which have been replaced by bit values predetermined by values of bits which are determined to provide 0 for a difference result. Thus, the number of signal changes decreases. As a result, the motion estimation apparatus which consumes less power without any decrease in calculation accuracy can be provided.